package leetcode.easy.q118;

import java.util.ArrayList;
import java.util.List;

public class Q {
}

class Solution {
    /**
     * dp[0]=[1]
     * dp[1]=[1,1]
     * dp[2]=[1,2,1]
     * ...
     * i<numRows 0<j<i-1
     * dp[i][0]=1
     * dp[i][j]=dp[i-1][j-1]+dp[i-1][j]
     * dp[i][i-1]=1
     */
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> resultList = new ArrayList();
        if (numRows > 0) {
            List<Integer> row1 = new ArrayList();
            row1.add(1);
            resultList.add(row1);
        }
        if (numRows > 1) {
            List<Integer> row2 = new ArrayList();
            row2.add(1);
            row2.add(1);
            resultList.add(row2);
        }
        for (int i = 2; i < numRows; i++) {
            List<Integer> row = new ArrayList();
            List<Integer> lastRow = resultList.get(i - 1);
            resultList.add(row);
            row.add(1);
            for (int j = 1; j < i; j++) {
                row.add(lastRow.get(j - 1) + lastRow.get(j));
            }
            row.add(1);
        }
        return resultList;
    }
}